package com.yeung.swordoffer;

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 */
public class 树的子结构 {
    /**
     * 因为有 左右孩子, 所以 采用递归方式来进行验证
     *
     * @param root1
     * @param root2
     * @return
     */
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //约定空树不是任意一个树的子结构
        if (root2 == null) return false;
        if (root1 == null && root2 != null) return false;

        //以中序的方式进行递归验证
        boolean flag = false;
        if (root1.val == root2.val)
            //查看子树是否相等
            flag = isSubTree(root1, root2);
        //如果根节点不匹配
        if (!flag) {
            flag = HasSubtree(root1.left, root2);
            //如果左子树不匹配
            if (!flag) {
                //此时的flag是右子树的匹配情况
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }

    static boolean isSubTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) return true;
        if (root1 == null && root2 != null) return false;
        if (root1.val == root2.val) {
            return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
        } else return false;
    }
}
